4483.
The kid who learned to count
The young kid works as a
controller on a ferry. His task is to ensure that the ferry does not sink due
to exceeding its weight capacity. Today, there are only two tickets left on the
ferry, along with the ability to carry an additional k kilograms.
In this forest,
there is a single long road along which the animals live. Help the young kid determine
whether he can find two passengers within a given section of the forest.
Input. The first line contains
two integers n (2 ≤ n ≤ 10⁶) and k (1
≤ k ≤ 10⁹) – the number of animals in the forest and
the remaining weight capacity of the ferry, respectively.
The second line contains n
integers – the weights of each animal.
The next line contains an
integer m (1 ≤ m ≤ 10⁵) – the number of
queries.
Each of the following m
lines contains three integers t, l, r:
·
If t = 1, then 1 ≤ l < r ≤ n – check whether it is
possible to select two passengers among the animals in the range [l; r].
·
If t = 2, then 1 ≤ l ≤ n, 1 ≤ r ≤ 109 – update the weight of the
animal at index l to r kilograms.
Output. For each query of type 1, print “Yes” if the young goat
can find two passengers within the specified range, and “No” otherwise.
A
query of type 2 means that the weight of the
animal at index l has
been updated to r
kilograms.
|
Sample
input |
Sample output |
|
6 9 1 3 1 6 6 7 8 1 1 6 1 1 2 2 4 7 1 4 5 1 5 6 2 1 7 2 3 8 1 1 6 |
Yes Yes No No Yes |
SOLUTION
data structures – segment tree, single modification
A segment tree can be
built to maintain the two smallest values in each range. However, in this
problem, we are not interested in the exact minimum values but rather in the
existence of two numbers whose sum does not exceed k.
The weights of the
passengers are stored in the leaves of the segment tree. The internal nodes
hold values according to the following rules:
·
If the sum of the two smallest values in the left and right
subtrees does not exceed k, then there exist two suitable passengers in
the range [l; r]. In this case, store 0 in the node corresponding to the interval [l;
r].
·
Otherwise, store the minimum value of its two child nodes.
Processing the quesries.
·
If the minimum value in the rang e [l; r] is 0, then there exist two passengers whose
total weight meets the condition, so the answer is “Yes”.
·
Otherwise, the answer is “No”.
Example
Let’s build a segment tree
for k = 9 and passenger weights 7, 3, 8, 7, 6, 7.
Among the fundamental
segments,
only the node
corresponding to [1; 6] will contain 0.
Algorithm implementation
Declare
an array SegTree to store the
segment tree. The weights of the animals are stored in the array a.
#define MAX 1000010
#define MAX_INT 1050000000
int SegTree[4*MAX];
int a[MAX];
The
function f merges the values of the child nodes in the segment
tree. The segment tree supports the minimum operation. However, if the sum of
the values in the left and right child nodes does not exceed k, return 0.
Additionally,
if at least one of the child nodes already contains 0, this means that two
suitable passengers exist in its range, so we also return 0.
int f(int a, int b)
{
if (a == 0 || b == 0 || a + b <= k) return
0;
return min(a,b);
}
The
function BuildTree constructs the segment tree. It takes as input the index of the
current node v and the boundaries lpos and rpos
corresponding to node v. The function f is used to merge
the values of the child nodes.
void BuildTree(int v, int lpos, int rpos)
{
if (lpos == rpos)
SegTree[v] = a[lpos];
else
{
int mid = (lpos + rpos) / 2;
BuildTree(2 * v, lpos, mid);
BuildTree(2 * v + 1, mid + 1, rpos);
SegTree[v] = f(SegTree[2 * v], SegTree[2 * v + 1]);
}
}
The
function Query processes a range query on [left; right].
The node v corresponds to the segment [lpos, rpos].
·
If
there exist two passengers in the range [left, right] whose total weight does not exceed k, the function Query returns 0.
·
Otherwise,
it returns the minimum passenger weight in the given range.
int Query(int v, int lpos, int rpos, int left, int right)
{
if (left > right) return MAX_INT;
if ((lpos == left) && (rpos == right)) return SegTree[v];
int mid = (lpos + rpos) / 2;
return f(Query(2 * v, lpos, mid, left, min(right, mid)),
Query(2 * v + 1,
mid + 1, rpos, max(left, mid + 1), right));
}
The function Update updates the value of the element at index pos, assigning
it val. The node v corresponds to the segment [lpos, rpos].
void Update(int v, int lpos, int rpos, int pos, int val)
{
if (lpos == rpos)
SegTree[v] = val;
else
{
int mid = (lpos + rpos) / 2;
if (pos <=
mid) Update(2 * v, lpos, mid, pos, val);
else Update(2 * v + 1,
mid + 1, rpos, pos, val);
SegTree[v] = f(SegTree[2 * v],
SegTree[2 * v + 1]);
}
}
The main part of the program. Read the weights of the animals into the array a,
starting from index 0.
scanf("%d %d",&n,&k);
for (i = 0; i < n; i++) scanf("%d",&a[i]);
Build a segment tree based on
the elements of the array a[0..n – 1].
BuildTree(1,0,n-1);
Process the queries
sequentially.
scanf("%d",&q);
for (j = 0; j < q; j++)
{
scanf("%d %d %d",&t,&l,&r);
if (t == 1)
{
int Res = Query(1,0,n-1,l-1,r-1);
if (Res == 0) printf("Yes\n");
else printf("No\n");
}
else
Update(1,0,n-1,l-1,r) ;
}